package algorithme;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class RandomBoruvka extends Boruvka {

	public Graphe appliquer(Graphe graphe) {
		List<Arete> aretes = new ArrayList<Arete>(graphe.getAretes());
		List<Arete> l = new ArrayList<Arete>();
		Map<Arete, Arete> aretes_originales = pondererAretes(aretes, l);

		Graphe r = doRandomBoruvka(new Graphe(l));
		Graphe result = new Graphe();
		for (Arete a : r.getAretes())
			result.ajouterArete(aretes_originales.get(a));
		return result;
	}

	protected Graphe doRandomBoruvka(Graphe g) {
		if(g.nbSommets()<=1)
			return g;
		List<Arete> acpm = new ArrayList<Arete>();
		Random rand = new Random();
		//Etape 1
		phaseBoruvka(g, acpm);
		phaseBoruvka(g, acpm);
		phaseBoruvka(g, acpm);
		Graphe G1 = g;
		//Etape 2
		Graphe G2 = new Graphe(G1);
		Collection<Arete> to_del = new ArrayList<Arete>();
		for (Arete a : G1.getAretes()) {
			if (rand.nextBoolean())
				to_del.add(a);
		}
		for (Arete a: to_del)
			G2.supprimerArete(a);
		//Etape 3
		if (G2.nbSommets() <= 1)
			return new Graphe(acpm);
		Foret F2 = new Foret(doRandomBoruvka(G2));
		//Etape 4
		if (F2.nbSommets()<=1)
			return new Graphe(acpm);
		Graphe G3 = new Graphe(G1);
		for (Arete a : G1.getAretes()) {
			// si a n'appartient pas à F2
			if(!F2.contient(a))
				//si les deux sommets appartiennent au même arbre
				if(a.getU() < F2.nbSommets() && a.getV() < F2.nbSommets() && F2.arbre(a.getU())==F2.arbre(a.getV()) && F2.arbre(a.getU()) != -1){
					if(a.getPoids()>F2.ancetreCommun(a.getU(), a.getV()))
						G3.supprimerArete(a);
				}
		}
		//Etape 5
		Graphe F3 =  doRandomBoruvka(G3);
		//Etape6
		Collection<Arete> CunionF3 = new HashSet<Arete>(F3.getAretes());
		CunionF3.addAll(G1.getAretes());
		return new Graphe(CunionF3);
	}

	@Override
	public String getName() {
		return "Random Boruvka";
	}
}
